import numpy as np
inf = 100000
def Floyd(adjMatrix,u,v):
    #Get the min length path from vertex u to vertex v in the Graph(V,E)
    distMatrix = adjMatrix
    parent = np.ones(adjMatrix.shape,int)*-1
    # the number of vertexes of Graph
    n = len(adjMatrix)
    #init of parent matrix
    for i in range(n):
        for j in range(n):
            if i != j and adjMatrix[i,j] < inf:
                parent[i][j] = i
    print('parent')
    print(parent)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if distMatrix[i,j] > distMatrix[i,k] + distMatrix[k,j]:
                    distMatrix[i,j] = distMatrix[i,k] + distMatrix[k,j]
                    parent[i,j] = parent[k,j]

    print("distMatrix")
    print(distMatrix)
    print("parent")
    print(parent)
    #find the path from u to v
    tmp = parent[u][v]
    print(v,end="")
    while(True):
        if tmp == u:
            print("<-",u)
            break
        else:
            print("<-",parent[u][tmp])
            tmp = parent[u][tmp]
    







adj = 'adjMatrix.txt'

with open(adj, encoding = 'utf-8') as f:
    adjMatrix = np.loadtxt(adj,int)
    print("adjMatrix")
    print(adjMatrix)
    u = int(input("u: "))
    v = int(input("v: "))
    Floyd(adjMatrix,u,v)
